#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 

vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};

static bool prime(int number) {
    if (number <= primes.back())
        return find(primes.begin(), primes.end(), number) != primes.end();
    
    if (number % 2 == 0) 
        return false;

    for (int i = 3; i * i <= number; i += 2) {
        if (number % i == 0) 
            return false;
    }
    primes.push_back(number);
    return true;
}

static int prime_summations(int number) {
    vector<pair<int, int>> v;
    for (int i = 0; primes[i] < number; ++i) 
        v.push_back({primes[i], number - primes[i]});
    
    int ans = 0;
    while (!v.empty()) {
        auto p = v.back();
        v.pop_back();

        if (p.first > p.second)
            continue;

        if (prime(p.second)) 
            ++ans; 

        for (int i = p.first; i < p.second; ++i) {
            if (prime(i)) {
                v.push_back({i, p.second - i});
            }
        }
    }
    return ans;
}

int main() {
    for (int i = 61; ; ++i) {
        int s = prime_summations(i);
        cout << i << ' ' << s << endl;
        if (s > 5000)   // i == 71
            break;
    }
}